package com.summli.basic.class09;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;

/**
 * 给定一个由字符串组成的数组strs，
 * 必须把所有的字符串拼接起来，
 * 返回所有可能的拼接结果中，字典序最小的结果
 * 字典序：如果两个字符串长度一样，直接认为是k进制的正数进行比较
 * 	如果两个字符串长度不一样的话，后面进行补齐，补零，
 * 	零认为比字母的任何一个ASCII码值要小，Java中compareTo方法比较的是字典序
 */
public class Code01_LowestLexicography {
    public static String lowestString1(String[] strs){
        if(strs == null){
            return null;
        }
        ArrayList<String> resultList = new ArrayList<>();
        HashSet<Integer> useSet = new HashSet<>();
        process(strs,useSet,"",resultList);
        String result = resultList.get(0);
        for (int i = 1; i < resultList.size(); i++) {
            result = result.compareTo(resultList.get(i))>0?resultList.get(i):result;
        }
        return result;
    }

    private static void process(String[] strs, HashSet<Integer> useSet, String tempResult,ArrayList<String> resultList) {
        if(useSet.size() == strs.length){
            resultList.add(tempResult);
            return;
        }
        for (int i = 0; i < strs.length; i++) {
            if(!useSet.contains(i)){
                useSet.add(i);
                process(strs,useSet,tempResult+strs[i],resultList);
                useSet.remove(i);
            }
        }

    }

    public static String lowestString2(String[] strs) {
        if(strs == null){
            return null;
        }
        Arrays.sort(strs,new MyCompatator());
        String result = "";
        for (int i = 0; i < strs.length; i++) {
            result += strs[i];
        }
        return result;
    }

    public static class MyCompatator implements Comparator<String> {

        @Override
        public int compare(String o1, String o2) {
            return (o1+o2).compareTo(o2+o1);
        }
    }

    // for test
    public static String generateRandomString(int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 5);
            ans[i] = (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    // for test
    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    // for test
    public static String[] copyStringArray(String[] arr) {
        String[] ans = new String[arr.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = String.valueOf(arr[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int arrLen = 6;
        int strLen = 5;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr1 = generateRandomStringArray(arrLen, strLen);
            String[] arr2 = copyStringArray(arr1);
            if (!lowestString1(arr1).equals(lowestString2(arr2))) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
}
